
package main.old.new_2023.last.month_9;


import java.util.*;

/**
 * @Description: todo 210. 课程表 II
 * 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
 * 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
 * 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
 * todo 630. 课程表 III
 * 这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，
 * 其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
 * 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
 * 返回你最多可以修读的课程数目。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution0912 {

    //课程表 III -贪心算法+优先队列
    public int scheduleCourse(int[][] courses) {
        //按照 截止日期排序
        Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));
        //优先队列，按照需要读的时间排序，加入课程时大于总时长，抛出需要时间最长的一个
        PriorityQueue<Integer> queue= new PriorityQueue<>((a,b)->b-a);
        //天数
        int sum = 0;
        for (int[] course:courses){
            int days = course[0];
            int limitDay = course[1];
            queue.add(days);
            sum +=days;
            //超了
            if (sum > limitDay){
                Integer maxDay = queue.poll();
                sum -= maxDay;
            }
        }
        return queue.size();
    }

    //课程表 II
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //判断学不学的完
        List<Integer> result = new LinkedList<>();
        //度数存储
        int[] courseCount = new int[numCourses];
        //关联关系存储
        List<List<Integer>> courseRelation = new ArrayList<>();
        for (int i=0;i<numCourses;i++){
            courseRelation.add(new ArrayList<>());
        }
        for (int[] pre:prerequisites){
            courseCount[pre[0]] = courseCount[pre[0]]+1;
            courseRelation.get(pre[1]).add(pre[0]);
        }
        //度为0
        Queue<Integer> courses = new LinkedList<>();
        for (int i = 0;i<numCourses;i++){
            if (courseCount[i] == 0){
                courses.add(i);
            }
        }
        while (!courses.isEmpty()){
            Integer course = courses.poll();
            result.add(course);
            if (courseRelation.get(course).size() >0){
                for (Integer temp:courseRelation.get(course)){
                    if (--courseCount[temp] == 0){
                        courses.add(temp);
                    }
                }
            }
        }
        int[] ints = new int[0];
        if (result.size() == numCourses){
            ints = new int[numCourses];
            for (int i = 0;i<numCourses;i++){
                ints[i] = result.get(i);
            }
        }
        return ints;
    }

    public static void main(String[] args) {
        int[][] ints = new int[0][];
        Solution0912 test = new Solution0912();
        test.findOrder(2,ints);
    }

}
